{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Subsequence of Size K With the Largest Even Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestEvenSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #长度为 K 的最大偶数和子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> 。找出&nbsp;<code>nums</code> 长度为 <code>k</code> 的所有子序列中的 <strong>最大偶数和</strong> 。<br />\n",
    "返回<strong>此总和</strong>，如果此总和不存在，则返回 <code>-1</code>。<br />\n",
    "<strong>子序列</strong> 是一个数组，可以通过删除一些元素或不删除任何元素而从另一个数组派生，而不改变其余元素的顺序。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [4,1,5,3,1], k = 3\n",
    "<strong>输出:</strong> 12\n",
    "<strong>解释:</strong>\n",
    "具有最大可能偶数和的子序列是[4,5,3]。它的和为 4 + 5 + 3 = 12\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [4,6,2], k = 3\n",
    "<strong>输出:</strong> 12\n",
    "<strong>解释:</strong>\n",
    "具有最大可能偶数和的子序列是[4,6,2]。它的和为 4 + 6 + 2 = 12\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,3,5], k = 1\n",
    "<strong>输出:</strong> -1\n",
    "<strong>解释:</strong>\n",
    "长度为 1 的 NUM 的子序列没有偶数和。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>Constraints:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [subsequence-of-size-k-with-the-largest-even-sum](https://leetcode.cn/problems/subsequence-of-size-k-with-the-largest-even-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [subsequence-of-size-k-with-the-largest-even-sum](https://leetcode.cn/problems/subsequence-of-size-k-with-the-largest-even-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,1,5,3,1]\\n3', '[4,6,2]\\n3', '[1,3,5]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        base = sum(nums[:k])\n",
    "        if base % 2 == 0:\n",
    "            return base \n",
    "        rest = [[] for _ in range(2)]\n",
    "        odd_flag = False \n",
    "        even_flag = False\n",
    "        for x in nums[k:]:\n",
    "            if x % 2:\n",
    "                if odd_flag:\n",
    "                    continue \n",
    "                else:\n",
    "                    rest[1].append(x)\n",
    "                    odd_flag = True \n",
    "                    if even_flag:\n",
    "                        break\n",
    "            else:\n",
    "                if even_flag:\n",
    "                    continue\n",
    "                else:\n",
    "                    rest[0].append(x)\n",
    "                    even_flag = True \n",
    "                    if odd_flag:\n",
    "                        break \n",
    "        a, b = -inf, -inf\n",
    "        for i in range(k - 1, -1, -1):\n",
    "            if nums[i] % 2:\n",
    "                if rest[0]:\n",
    "                    a = base + rest[0][0] - nums[i]\n",
    "                    break\n",
    "        for i in range(k - 1, -1, -1):\n",
    "            if nums[i] % 2 == 0:\n",
    "                if rest[1]:\n",
    "                    b = base + rest[1][0] - nums[i]\n",
    "                    break\n",
    "        ans = max(a, b)\n",
    "        return ans if ans != -inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        arr1, arr2 = [], []\n",
    "        for x in nums:\n",
    "            if x % 2: arr1.append(x) \n",
    "            else: arr2.append(x)\n",
    "\n",
    "        arr1.sort(reverse=True)\n",
    "        arr2.sort(reverse=True)\n",
    "        m, n = len(arr1), len(arr2)\n",
    "        if n == 0 and k % 2 == 1:\n",
    "            return -1\n",
    "        i, j = 0, k\n",
    "        if n < k:\n",
    "            while j > n:\n",
    "                i += 2\n",
    "                j -= 2\n",
    "        if i > m:\n",
    "            return -1\n",
    "        s = sum(arr1[:i]) + sum(arr2[:j])\n",
    "        ans = s\n",
    "        i += 2\n",
    "        j -= 2\n",
    "        while i <= m and j >= 0:\n",
    "            s += arr1[i-1] + arr1[i-2] - arr2[j+1] - arr2[j]\n",
    "            ans = max(ans, s)\n",
    "            i += 2\n",
    "            j -= 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) < k: return -1\n",
    "        if len(nums) == k and sum(nums) % 2 != 0: return -1\n",
    "\n",
    "        co = nums.copy()\n",
    "        co.sort(reverse = True)\n",
    "\n",
    "        if k == 1:\n",
    "            for s in co:\n",
    "                if s%2 == 0: return s\n",
    "\n",
    "        odd = []\n",
    "        even = []\n",
    "        for i in range(k):\n",
    "            if co[i] % 2 == 0:\n",
    "                even.append(co[i])\n",
    "            else: \n",
    "                odd.append(co[i])\n",
    "        \n",
    "\n",
    "        s = sum(co[:k])\n",
    "        \n",
    "\n",
    "        if len(odd) % 2 != 0:\n",
    "            se = -1\n",
    "            so = -1\n",
    "            fueven = []\n",
    "            fuodd = []\n",
    "            for m in co[k:]:\n",
    "                if m % 2 ==0:\n",
    "                    fueven.append(m)\n",
    "                else:\n",
    "                    fuodd.append(m)\n",
    "\n",
    "            # change one even to odd\n",
    "            if len(even) > 0 and len(fuodd) > 0:\n",
    "                se = s - even[-1] + fuodd[0]\n",
    "\n",
    "            # change one odd to even\n",
    "            if len(odd) > 0 and len(fueven) > 0:\n",
    "                so = s - odd[-1] + fueven[0]\n",
    "            s = max(se, so)\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "        # odd = dict()\n",
    "        # even = dict()\n",
    "        # for i in range(len(nums)):\n",
    "        #     if nums[i] % 2 == 0:\n",
    "        #         even[str(nums[i])] = i\n",
    "        #     else: \n",
    "        #         odd[str(nums[i])] = i\n",
    "\n",
    "        # odd = sorted(odd.items(), key = lambda x:x[0])\n",
    "        # even = sorted(even.items(), key = lambda x:x[0])\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        j=[]\n",
    "        o=[]\n",
    "        s=0\n",
    "        for i in nums:\n",
    "            if i%2:\n",
    "                j.append(i)\n",
    "            else:\n",
    "                heappush(o,i)\n",
    "                s+=i\n",
    "        while len(o)>k:\n",
    "            s-=heappop(o)\n",
    "        res=-1\n",
    "        if len(o)==k:\n",
    "            res=s\n",
    "        elif (k-len(o))%2 and o:\n",
    "            s-=heappop(o)\n",
    "        l=len(o)\n",
    "        j.sort(reverse=True)\n",
    "        for i in range(1,len(j),2):\n",
    "            s+=j[i]+j[i-1]\n",
    "            l+=2\n",
    "            while len(o)>1 and l>k:\n",
    "                s-=heappop(o)\n",
    "                s-=heappop(o)\n",
    "                l-=2\n",
    "            if l==k:\n",
    "                res=max(res,s)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        ls1=[]\n",
    "        c1=0\n",
    "        ls2=[]\n",
    "        c2=0\n",
    "        for n in nums:\n",
    "            if n%2==0:\n",
    "                ls2.append(n)\n",
    "                c2+=1\n",
    "            else:\n",
    "                ls1.append(n)\n",
    "                c1+=1\n",
    "        i1,i2=0,0\n",
    "        ls1.sort(reverse=True)\n",
    "        ls2.sort(reverse=True)\n",
    "        ans=0\n",
    "        if k%2==1:\n",
    "            if c2==0:\n",
    "                return -1\n",
    "            k-=1\n",
    "            ans+=ls2[i2]\n",
    "            i2+=1\n",
    "        while k>0:\n",
    "            k-=2\n",
    "            if c1-i1<2 and c2-i2<2:\n",
    "                return -1\n",
    "            elif c1-i1<2:\n",
    "                ans+=ls2[i2]+ls2[i2+1]\n",
    "                i2+=2\n",
    "            elif c2-i2<2:\n",
    "                ans+=ls1[i1]+ls1[i1+1]\n",
    "                i1+=2\n",
    "            else:\n",
    "                if ls1[i1]+ls1[i1+1]>ls2[i2]+ls2[i2+1]:\n",
    "                    ans+=ls1[i1]+ls1[i1+1]\n",
    "                    i1+=2\n",
    "                else:\n",
    "                    ans+=ls2[i2]+ls2[i2+1]\n",
    "                    i2+=2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        #如果全要\n",
    "        if k==n:\n",
    "            t=sum(nums)\n",
    "            if t%2:return -1\n",
    "            else:return t\n",
    "        nums.sort()\n",
    "        #如果正好就是这些高干，全部装车，，发送\n",
    "        w= sum(nums[-k:])\n",
    "        if w%2==0:return w\n",
    "        #如果只要一个，，找个最大的偶数，\n",
    "        if k==1:\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if nums[j]%2==0:\n",
    "                    return nums[j] \n",
    "            return -1 \n",
    "        #奇偶数分开    \n",
    "        ji =[]\n",
    "        ou=[]\n",
    "        for v in nums:\n",
    "            if v%2:ji.append(v)\n",
    "            else:ou.append(v)\n",
    "        #偶数一个没有，k还是奇数 \n",
    "        if len(ou) ==0 and k%2:return -1\n",
    "        #如果只有一个奇数，，把她赶出去，，男人们自在的洗澡\n",
    "        a=len(ji)\n",
    "        if a==1:return sum(ou[-k:])\n",
    "        #焊接起来\n",
    "        la=ou +ji[::-1]\n",
    "        ww=v =sum(la[:k]) \n",
    "        if v%2==0:\n",
    "            he =v    \n",
    "        else:\n",
    "            he =-1\n",
    "        g=k\n",
    "        #滑动窗口\n",
    "        while g<n:\n",
    "            ww += la[g] -la[g-k] \n",
    "            if ww%2==0 and ww>he: #长得漂亮，身材好，选中\n",
    "                he =ww\n",
    "            g+=1 \n",
    "        return he     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        curr = 0\n",
    "        res = -1\n",
    "        min_o = float('inf')\n",
    "        min_j = float('inf')\n",
    "        for i in range(k):\n",
    "            curr += nums[i]\n",
    "            if nums[i] % 2 == 0:\n",
    "                min_o = min(min_o, nums[i])\n",
    "            else:\n",
    "                min_j = min(min_j, nums[i])\n",
    "        if curr % 2 == 0:\n",
    "            return curr\n",
    "        for i in range(k, len(nums)):\n",
    "            if nums[i] % 2 != 0:\n",
    "                if min_o != float('inf'):\n",
    "                    tmp = curr\n",
    "                    tmp -= min_o\n",
    "                    tmp += nums[i]\n",
    "                    if tmp % 2 == 0 and tmp > res:\n",
    "                        res = tmp\n",
    "            else:\n",
    "                if min_j != float('inf'):\n",
    "                    tmp = curr\n",
    "                    tmp -= min_j\n",
    "                    tmp += nums[i]\n",
    "                    if tmp % 2 == 0 and tmp > res:\n",
    "                        res = tmp\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        l1 = []\n",
    "        l2 = []\n",
    "        curr = 0\n",
    "        res = -1\n",
    "        for i in range(k):\n",
    "            curr += nums[i]\n",
    "            if nums[i] % 2 == 0:\n",
    "                l1.append(nums[i])\n",
    "            else:\n",
    "                l2.append(nums[i])\n",
    "        if curr % 2 == 0:\n",
    "            return curr\n",
    "        for i in range(k, len(nums)):\n",
    "            if nums[i] % 2 != 0:\n",
    "                if l1:\n",
    "                    tmp = curr\n",
    "                    tmp -= l1[-1]\n",
    "                    tmp += nums[i]\n",
    "                    if tmp % 2 == 0 and tmp > res:\n",
    "                        res = tmp\n",
    "            else:\n",
    "                if l2:\n",
    "                    tmp = curr\n",
    "                    tmp -= l2[-1]\n",
    "                    tmp += nums[i]\n",
    "                    if tmp % 2 == 0 and tmp > res:\n",
    "                        res = tmp\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        even_nums = []\n",
    "        odd_nums = []\n",
    "        for x in nums[::-1]:\n",
    "            if x % 2:\n",
    "                odd_nums.append(x)\n",
    "            else:\n",
    "                even_nums.append(x)\n",
    "        max_odd_nums = len(odd_nums)\n",
    "        choose_even_nums = []\n",
    "        choose_odd_nums = []\n",
    "        t = 0\n",
    "        if len(even_nums) >= k:\n",
    "            choose_even_nums = copy.deepcopy(even_nums[:k])\n",
    "            ans = sum(choose_even_nums)\n",
    "        else:\n",
    "            choose_even_nums = copy.deepcopy(even_nums)\n",
    "            t = k - len(even_nums)\n",
    "            if t % 2:\n",
    "                t += 1\n",
    "                if not choose_even_nums:\n",
    "                    return -1\n",
    "                choose_even_nums.pop(-1)\n",
    "            choose_odd_nums = copy.deepcopy(odd_nums[:t])\n",
    "            ans = sum(choose_even_nums) + sum(choose_odd_nums)\n",
    "        if ans % 2:\n",
    "            return -1\n",
    "        temp = ans\n",
    "        while temp >= ans and len(choose_even_nums) >= 2:\n",
    "            t += 2\n",
    "            print(t)\n",
    "            if t > max_odd_nums:\n",
    "                return ans\n",
    "            temp -= choose_even_nums.pop(-1)\n",
    "            temp -= choose_even_nums.pop(-1)\n",
    "            temp += odd_nums[t-2]\n",
    "            temp += odd_nums[t-1]\n",
    "            if temp >= ans:\n",
    "                ans = temp\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "\n",
    "        minOdd = minEven = 10 ** 5\n",
    "        preSum = 0\n",
    "        for i in range(k):\n",
    "            preSum += nums[i]\n",
    "            if nums[i] % 2:\n",
    "                minOdd = nums[i]\n",
    "            else:\n",
    "                minEven = nums[i]\n",
    "        \n",
    "        if preSum % 2 == 0: return preSum\n",
    "        \n",
    "        ans = -1\n",
    "        for i in range(k, len(nums)):\n",
    "            if nums[i] % 2 and (preSum - minEven + nums[i]) % 2 == 0:\n",
    "                ans = max(ans, preSum - minEven + nums[i])\n",
    "            elif nums[i] % 2 == 0 and (preSum - minOdd + nums[i]) % 2 == 0:\n",
    "                ans = max(ans, preSum - minOdd + nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        result, n = sum(nums[-k:]), len(nums)\n",
    "        if result & 1:\n",
    "            result, x = -1, result\n",
    "            left, right = [-1, -1], [-1, -1]\n",
    "            for i in range(n - k):\n",
    "                left[nums[i] & 1] = nums[i]\n",
    "            for i in range(n-1, n-k-1, -1):\n",
    "                right[nums[i] & 1] = nums[i]\n",
    "            if left[0] >= 0 and right[1] >= 0:\n",
    "                result = x + left[0] - right[1]\n",
    "            if left[1] >= 0 and right[0] >= 0:\n",
    "                result = max(result, x + left[1] - right[0])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 分类讨论\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = -1\n",
    "        # 选取k次，获得最大偶数和\n",
    "        # 排序取逆序\n",
    "        # 排序后如果最大的k项总和本身就是偶数，则合法\n",
    "        # 如果是总和是奇数\n",
    "        # 则抛弃k个中最小的奇数，用不在其中的最大的偶数替换。\n",
    "        # 或者抛弃k个中最小的偶数，用不在其中的最大奇数替换\n",
    "        # 两者取总和更大的\n",
    "        nums.sort(reverse = True)\n",
    "        tSum = sum(nums[:k])\n",
    "        if tSum % 2 == 0:\n",
    "            return tSum\n",
    "        else:\n",
    "            # 情况1:抛弃k个中最小的奇数，用不在其中的最大的偶数替换。\n",
    "            p1 = k - 1\n",
    "            while p1 >= 0 and nums[p1] % 2 == 0:\n",
    "                p1 -= 1\n",
    "\n",
    "            p2 = k \n",
    "            while p2 < n and nums[p2] % 2 == 1:\n",
    "                p2 += 1\n",
    "\n",
    "            if p1 >= 0 and p2 < n: # 说明找到了\n",
    "                ans = max(ans, tSum - abs(nums[p2] - nums[p1]))\n",
    "\n",
    "            ## 情况2：抛弃k个中最小的偶数，用不在其中的最大奇数替换\n",
    "            p3 = k-1\n",
    "            while p3 >= 0 and nums[p3] % 2 == 1:\n",
    "                p3 -= 1\n",
    "\n",
    "            p4 = k \n",
    "            while p4 < n and nums[p4] % 2 == 0:\n",
    "                p4 += 1\n",
    "            \n",
    "            if p3 >= 0 and p4 < n: # 说明找到了\n",
    "                ans = max(ans, tSum - abs(nums[p4] - nums[p3]))\n",
    "\n",
    "            return ans \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def largestEvenSum(self, nums, k):\n",
    "        nums.sort(reverse = True)\n",
    "        if k > len(nums):\n",
    "            return -1\n",
    "        t = sum(nums[:k])\n",
    "        if t % 2 == 0:\n",
    "            return t \n",
    "        m1, m2, n1, n2 = -1, -1, -1, -1\n",
    "        for x in nums[:k]:\n",
    "            if x % 2 == 1:\n",
    "                m1 = x\n",
    "            else:\n",
    "                m2 = x\n",
    "        for x in nums[k:]:\n",
    "            if x % 2 == 1:\n",
    "                n1 = max(n1, x)\n",
    "            else:\n",
    "                n2 = max(n2, x)\n",
    "        if min(m1, n2) > -1 and min(m2, n1) > -1:\n",
    "            return t - min((m1 - n2), (m2 - n1))\n",
    "        if min(m1, n2) > -1:\n",
    "            return t - m1 + n2 \n",
    "        if min(m2, n1) > -1:\n",
    "            return t - m2 + n1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 100 ms ... 43 % ... 29 MB ... 0 %\n",
    "        #  time: O(nlogn)\n",
    "        # space: O(1)\n",
    "        \n",
    "        nums.sort(reverse=True)\n",
    "        res = sum(nums[:k])\n",
    "        if not res % 2:\n",
    "            return res\n",
    "        smallest_odd, smallest_eve = -1, -1\n",
    "        for i in range(k):\n",
    "            if nums[i] % 2:\n",
    "                smallest_odd = nums[i]\n",
    "            else:\n",
    "                smallest_eve = nums[i]\n",
    "        largest_odd, largest_eve = -1, -1\n",
    "        for i in range(k, len(nums)):\n",
    "            if nums[i] % 2:\n",
    "                if largest_odd == -1:\n",
    "                    largest_odd = nums[i]\n",
    "            else:\n",
    "                if largest_eve == -1:\n",
    "                    largest_eve = nums[i]\n",
    "        case1, case2 = -1, -1\n",
    "        if smallest_odd != -1 and largest_eve != -1:\n",
    "            case1 = res - smallest_odd + largest_eve\n",
    "        if smallest_eve != -1 and largest_odd != -1:\n",
    "            case2 = res - smallest_eve + largest_odd\n",
    "        return -1 if case1 == -1 and case2 == -1 else max(case1, case2)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 分类讨论\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = -1\n",
    "        # 选取k次，获得最大偶数和\n",
    "        # 排序取逆序\n",
    "        # 排序后如果最大的k项总和本身就是偶数，则合法\n",
    "        # 如果是总和是奇数\n",
    "        # 则抛弃k个中最小的奇数，用不在其中的最大的偶数替换。\n",
    "        # 或者抛弃k个中最小的偶数，用不在其中的最大奇数替换\n",
    "        # 两者取总和更大的\n",
    "        nums.sort(reverse = True)\n",
    "        tSum = sum(nums[:k])\n",
    "        if tSum % 2 == 0:\n",
    "            return tSum\n",
    "        else:\n",
    "            # 情况1:抛弃k个中最小的奇数，用不在其中的最大的偶数替换。\n",
    "            p1 = k - 1\n",
    "            while p1 >= 0 and nums[p1] % 2 == 0:\n",
    "                p1 -= 1\n",
    "\n",
    "            p2 = k \n",
    "            while p2 < n and nums[p2] % 2 == 1:\n",
    "                p2 += 1\n",
    "\n",
    "            if p1 >= 0 and p2 < n: # 说明找到了\n",
    "                ans = max(ans, tSum - abs(nums[p2] - nums[p1]))\n",
    "\n",
    "            ## 情况2：抛弃k个中最小的偶数，用不在其中的最大奇数替换\n",
    "            p3 = k-1\n",
    "            while p3 >= 0 and nums[p3] % 2 == 1:\n",
    "                p3 -= 1\n",
    "\n",
    "            p4 = k \n",
    "            while p4 < n and nums[p4] % 2 == 0:\n",
    "                p4 += 1\n",
    "            \n",
    "            if p3 >= 0 and p4 < n and nums[p3] % 2 == 0 and nums[p4] % 2 == 1: # 说明找到了\n",
    "                ans = max(ans, tSum - abs(nums[p4] - nums[p3]))\n",
    "\n",
    "            return ans \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "\n",
    "        minOdd = minEven = 10 ** 5\n",
    "        preSum = 0\n",
    "        for i in range(k):\n",
    "            preSum += nums[i]\n",
    "            if nums[i] % 2:\n",
    "                minOdd = nums[i]\n",
    "            else:\n",
    "                minEven = nums[i]\n",
    "        \n",
    "        if preSum % 2 == 0: return preSum\n",
    "        \n",
    "        ans = -1\n",
    "        for i in range(k, len(nums)):\n",
    "            if nums[i] % 2 and (preSum - minEven + nums[i]) % 2 == 0:\n",
    "                ans = max(ans, preSum - minEven + nums[i])\n",
    "            elif nums[i] % 2 == 0 and (preSum - minOdd + nums[i]) % 2 == 0:\n",
    "                ans = max(ans, preSum - minOdd + nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = -1\n",
    "        # 选取k次，获得最大偶数和\n",
    "        # 排序取逆序\n",
    "        # 排序后如果最大的k项总和本身就是偶数，则合法\n",
    "        # 如果是总和是奇数\n",
    "        # 则抛弃k个中最小的奇数，用不在其中的最大的偶数替换。\n",
    "        # 或者抛弃k个中最小的偶数，用不在其中的最大奇数替换\n",
    "        # 两者取总和更大的\n",
    "        nums.sort(reverse = True)\n",
    "        tSum = sum(nums[:k])\n",
    "        if tSum % 2 == 0:\n",
    "            return tSum\n",
    "        else:\n",
    "            # 情况1:抛弃k个中最小的奇数，用不在其中的最大的偶数替换。\n",
    "            p1 = k-1\n",
    "            while p1 >= 0 and nums[p1] % 2 == 0:\n",
    "                p1 -= 1\n",
    "\n",
    "            p2 = k \n",
    "            while p2 < n and nums[p2] % 2 == 1:\n",
    "                p2 += 1\n",
    "            if p1 >= 0 and p2 < n and nums[p1] % 2 == 1 and nums[p2] % 2 == 0: # 说明找到了\n",
    "                ans = max(ans, tSum - abs(nums[p2] - nums[p1]))\n",
    "\n",
    "            ## 情况2：抛弃k个中最小的偶数，用不在其中的最大奇数替换\n",
    "            p3 = k-1\n",
    "            while p3 >= 0 and nums[p3] % 2 == 1:\n",
    "                p3 -= 1\n",
    "\n",
    "            p4 = k \n",
    "            while p4 < n and nums[p4] % 2 == 0:\n",
    "                p4 += 1\n",
    "            \n",
    "            if p3 >= 0 and p4 < n and nums[p3] % 2 == 0 and nums[p4] % 2 == 1: # 说明找到了\n",
    "                ans = max(ans, tSum - abs(nums[p4] - nums[p3]))\n",
    "\n",
    "            return ans \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if k == 1:\n",
    "            v1 = -math.inf\n",
    "            for i in nums:\n",
    "                if i %2 == 0:\n",
    "                    v1 = max(v1, i)\n",
    "            if v1 == -math.inf:\n",
    "                return -1\n",
    "            return v1\n",
    "\n",
    "        nums.sort(reverse=True)\n",
    "        picked = nums[:k]\n",
    "        ss1 = sum(picked)\n",
    "        rest = nums[k:]\n",
    "        if sum(picked) % 2 == 0:\n",
    "            return sum(picked)\n",
    "        v1 = -math.inf\n",
    "        v2 = -math.inf\n",
    "        o1, o2 = math.inf, math.inf\n",
    "        for i in reversed(picked):\n",
    "            if i % 2 == 1:\n",
    "                o1 = i\n",
    "                break\n",
    "        for i in reversed(picked):\n",
    "            if i % 2 == 0:\n",
    "                o2 = i\n",
    "                break\n",
    "        for i in rest:\n",
    "            if i %2 == 0 and o1 != math.inf:\n",
    "                v1 = max(v1, ss1 - o1 + i)\n",
    "                break\n",
    "        for i in rest:\n",
    "            if i %2 == 1 and o2 != math.inf:\n",
    "                v2 = max(v2, ss1 - o2 + i)\n",
    "\n",
    "        ret = max(v1,v2)\n",
    "        if ret == -math.inf or ret == math.inf:\n",
    "            return -1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        arr=nums\n",
    "        arr.sort(reverse=True)\n",
    "        mxou=100001\n",
    "        mxji=100001\n",
    "        miou=100001\n",
    "        miji=100001\n",
    "        n=len(arr)\n",
    "        cnt=0\n",
    "        for i,v in enumerate(arr):\n",
    "            if i<k:\n",
    "                cnt+=v\n",
    "                if v%2==0:\n",
    "                    mxou=min(v,mxou)\n",
    "                else:\n",
    "                    mxji=min(v,mxji)\n",
    "            elif i>=k:\n",
    "                if v%2==0 and miou==100001:\n",
    "                    miou=v\n",
    "                elif v%2==1 and miji==100001:\n",
    "                    miji=v\n",
    "                elif miou!=100001 and miji!=100001:\n",
    "                    break\n",
    "        if cnt%2==0:\n",
    "            return cnt\n",
    "        ans=-1\n",
    "        if mxou!=100001 and miji!=100001:\n",
    "            ans=max(ans,cnt-mxou+miji)\n",
    "        if mxji!=100001 and miou!=100001:\n",
    "            ans=max(ans,cnt-mxji+miou)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        \n",
    "        if not sum(nums[:k]) & 1:\n",
    "            return sum(nums[:k])\n",
    "        minodd = -1\n",
    "        mineven = -1\n",
    "        for i in range(k - 1,-1,-1):\n",
    "            if nums[i] & 1 and minodd == -1:\n",
    "                minodd = nums[i]\n",
    "            if not nums[i] & 1 and mineven == -1:\n",
    "                mineven = nums[i]\n",
    "\n",
    "        maxeven = -1\n",
    "        maxodd = -1\n",
    "        for i in range(k,len(nums)):\n",
    "            if nums[i] & 1 and maxodd == -1:\n",
    "                maxodd = nums[i]\n",
    "            if not nums[i] & 1 and maxeven == -1:\n",
    "                maxeven = nums[i]\n",
    "        \n",
    "        if (maxeven == -1 or minodd == -1) and (maxodd == -1 or mineven == -1):\n",
    "            return -1\n",
    "        ans1,ans2 = 0,0\n",
    "        if maxeven != -1 and minodd != -1:\n",
    "            ans1 = sum(nums[:k]) - minodd + maxeven\n",
    "        if maxodd != -1 and mineven != -1:\n",
    "            ans2 = sum(nums[:k]) - mineven + maxodd\n",
    "        return max(ans1,ans2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestEvenSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(key=lambda x: -x) \n",
    "        mn1, mn2 = float('inf'), float('inf')\n",
    "        tot = 0 \n",
    "        n = len(nums) \n",
    "        for i in range(k):\n",
    "            tot += nums[i]\n",
    "            if nums[i]%2==0:\n",
    "                mn1 = min(mn1, nums[i]) \n",
    "            if nums[i]%2==1:\n",
    "                mn2 = min(mn2, nums[i]) \n",
    "        if tot % 2 == 0:\n",
    "            return tot \n",
    "        if k == n:\n",
    "            return -1 \n",
    "        mx1, mx2 = float('-inf'), float('-inf')\n",
    "        for i in range(k, n):\n",
    "            if nums[i]%2==0:\n",
    "                mx1 = max(mx1, nums[i])\n",
    "            if nums[i]%2==1:\n",
    "                mx2 = max(mx2, nums[i]) \n",
    "\n",
    "        if mn1 == float('inf'):\n",
    "            if mx1 == float('-inf'):\n",
    "                return -1 \n",
    "            return tot - mn2 + mx1 \n",
    "        if mx1 == float('-inf'):\n",
    "            return tot - mn1 + mx2 \n",
    "        if mx2 == float('-inf'):\n",
    "            return tot - mn2 + mx1 \n",
    "        return max(tot - mn1 + mx2, tot - mn2 + mx1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
